home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Moscow ML 1.42 / src / compiler / Sort.sml < prev    next >
Encoding:
Text File  |  1997-08-18  |  678 b   |  25 lines  |  [TEXT/R*ch]
  1. (* Merging and sorting *)
  2.  
  3. fun merge order =
  4.   let fun loop [] ys = ys
  5.         | loop xs [] = xs
  6.         | loop (xs as x::xr) (ys as y::yr) =
  7.             if order x y then 
  8.               x :: loop xr ys 
  9.             else 
  10.               y :: loop xs yr
  11.   in loop end;
  12.  
  13. fun sort order l =
  14.   let fun initList [] = []
  15.         | initList [e] = [[e]]
  16.         | initList (x1::x2::xs) =
  17.             (if order x1 x2 then [x1, x2] else [x2, x1]) :: initList xs
  18.       fun merge2 (xs1::xs2::xss) = merge order xs1 xs2 :: merge2 xss
  19.         | merge2 x = x
  20.       fun mergeAll [] = []
  21.         | mergeAll [xs] = xs
  22.         | mergeAll xss = mergeAll (merge2 xss)
  23.   in mergeAll(initList l) end
  24. ;
  25.